//70.爬楼梯
//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

//递归解法（暴力解法）
/*
int climbStairs(int n) 
{
    if(n <= 0)
        return 0;
    
    if(n == 1)
        return 1;
    if(n == 2)
        return 2;

    return climbStairs(n -1) + climbStairs(n -2);
}
*/

//滚动数组解法
//f(n) = f(n - 1) + f(n - 2)
//通过三个变量进行滚动，计算出f(n - 1) 和 f(n - 2)的值，即f(n)的值
int climbStairs(int n) 
{
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; ++i) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
}
